import java.util.List;

public class MySingleList {
    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val){
            this.val = val;
        }
    }

    public ListNode head;

    public void creatList(){
        ListNode Node1 = new ListNode(12);
        ListNode Node2 = new ListNode(23);
        ListNode Node3 = new ListNode(34);
        ListNode Node4 = new ListNode(45);
        ListNode Node5 = new ListNode(56);
        ListNode Node6 = new ListNode(67);
        ListNode Node7 = new ListNode(78);


        this.head = Node1;
        Node1.next = Node2;
        Node2.next = Node3;
        Node3.next = Node4;
        Node4.next = Node5;
        Node5.next = Node6;
        Node6.next = Node7;

    }

    public void printList(){
        ListNode curNode = head;
        while(curNode != null){
            System.out.print(curNode.val + " ");
            curNode = curNode.next;
        }
        System.out.println();
    }

    public int size(){
        ListNode curNode = head;
        int count = 0;
        while(curNode != null){
            count++;
            curNode = curNode.next;
        }
        return count;
    }

    public boolean contains(int key){
        boolean flag = false;
        ListNode curNode = head;
        while(curNode != null){
            if(curNode.val == key){
                flag = true;
                return flag;
            }
            curNode = curNode.next;
        }
        return flag;
    }

    //头插法
    public void addFirst(int data){
        ListNode Node = new ListNode(data);
        Node.next = head;
        head = Node;
    }

    //尾插法
    public void addLast(int data){
        ListNode Node = new ListNode(data);
        ListNode curNode = head;
        if(head == null){
            head = Node;
            return ;
        }
        while(curNode.next != null){
            curNode = curNode.next;
        }
        curNode.next = Node;
    }

    //插入
    public void addIndex(int val,int index){
        ListNode cur = head;
        ListNode node = new ListNode(val);
        if(index == 0){
            addFirst(val);
            return ;
        } else if (index == size()) {
            addLast(val);
            return ;
        } else if (index < 0 || index > size()) {
            return ;
        }
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        node.next = cur.next;
        cur.next = node;
    }

    //删除出现的第一个关键字 key
    public void delIndex(int key){
        if(head == null){
            return ;
        }
        if(head.val == key){
            head = head.next;
            return ;
        }
        ListNode cur = findKey1(key);
        if(cur == null){
            System.out.println("链表中没有该数");
            return ;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

    //找到关键字 key 的前一位
    public ListNode findKey1(int key){
        ListNode cur = head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除出现的全部关键字 key
    public void removeAllKey(int key){
        if(head == null){
            return ;
        }
        while(head.val == key){
            head = head.next;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
    }

    //清空链表
    public void clear(){
        ListNode cur = head;
        while(cur.next != null){
            ListNode curN = cur.next;
            cur.next = null;
            cur = curN;
        }
        head = null;
    }

    //反转链表
    public ListNode reverseList() {
        if(head == null)return head;
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
        return head;
    }

    //从指定位置反转打印
    public void printList(ListNode newHead){
        ListNode cur = newHead;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //返回链表的中间节点
    //方法1
    public ListNode middleNode1() {
        ListNode cur = head;
        int count = 1;
        while(cur.next != null){
            count++;
            cur = cur.next;
        }
        int dest = count/2;
        ListNode curN = head;
        for (int i = 0; i < dest ; i++) {
            curN = curN.next;
        }
        return curN;
    }

    //方法2
    public ListNode middleNode2() {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //返回倒数第K个节点

    //方法1
    public int kthToLast1(ListNode head, int k) {
        ListNode cur = head;
        int count = 1;
        while(cur.next != null){
            count++;
            cur = cur.next;
        }
        ListNode curN = head;
        for (int i = 0; i < count - k; i++) {
            curN = curN.next;
        }
        return curN.val;
    }

    //方法2
    public int kthToLast2(ListNode head, int k) {
        ListNode cur = head;
        int count = 1;
        while(cur.next != null){
            count++;
            cur = cur.next;
        }
        if(k <= 0 || k > count){
            return -1;
        }
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k - 1; i++) {
            fast = fast.next;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

    //合并两链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head1 = list1;
        ListNode head2 = list2;
        ListNode newH = new ListNode(0);
        ListNode tmpH = newH;
        while(head1 != null && head2 != null){
            if(head1.val <= head2.val){
                tmpH.next = head1;
                head1 = head1.next;
                tmpH = tmpH.next;
            }else{
                tmpH.next = head2;
                head2 = head2.next;
                tmpH = tmpH.next;
            }
        }
        return newH.next;
    }

    //链表分割
    public ListNode partition(ListNode pHead, int x) {
        ListNode new1 = new ListNode(0);
        ListNode curN1 = new1;
        ListNode new2 = new ListNode(0);
        ListNode curN2 = new2;
        ListNode cur = pHead;

        //采用尾插法
        while(cur != null){
            if(cur.val < x){
                if(curN1 == null){
                    curN1 = cur;
                    cur = cur.next;
                }else{
                    curN1.next = cur;
                    cur = cur.next;
                }
            }else{
                if(curN2 == null){
                    curN2 = cur;
                    cur = cur.next;
                }else{
                    curN2.next = cur;
                    cur = cur.next;
                }
            }
        }
        curN1.next = new2;
        return new1;
    }

    //判断是否为回文链表：
    public boolean chkPalindrome(ListNode A) {
        if(A == null)return false;
        ListNode fast = A;
        ListNode slow = A;
        //找到中间节点：
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;

        //反转：
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
            curN = cur.next;
        }

        //判断是否回文：
        // while(A != slow){
        //     if(A.val != slow.val){
        //         return false;
        //     }
        //     if(A.next == slow){
        //         return true;
        //     }
        //     A = A.next;
        //     slow = slow.next;
        // }
        // return true;

        while(A.val == slow.val){
            A = A.next;
            slow = slow.next;
            if(slow == A || A.next == slow){
                return true;
            }
        }
        return false;
    }

    //两链表相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)return null;
        ListNode pl = headA;
        ListNode ps = headB;
        int len1 = 0;
        int len2 = 0;
        while(pl.next != null){
            len1++;
            pl = pl.next;
        }
        while(ps.next != null){
            len2++;
            ps = ps.next;
        }
        int len = Math.abs(len1 - len2);
        if(len1 > len2){
            pl = headA;
            ps = headB;
        }else{
            pl = headB;
            ps = headA;
        }
        for (int i = 0; i < len; i++) {
            pl = pl.next;
        }
        while(pl != null && ps != null){
            if(pl == ps){
                return pl;
            }
            ps = ps.next;
            pl = pl.next;
        }
        return null;
    }

    //判断链表是否有环
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

    //求链表开始入环的第一个节点
    public ListNode detectCycle(ListNode head) {
        if(head == null)return null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null){
            return null;
        }
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }











}
